package com.leetcode.动态规划;

/**
 * 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

 nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。
 * @author LZF
 *
 */
public class L1035不相交的线 {
	
	public static void main(String[] args) {
		int result = maxUncrossedLines(new int[] {2,5,1,2,5}, new int[] {10,5,2,1,5,2});
		System.out.println(result);
	}
	/**
	 * 绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
	 * 直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，
	 * 且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
	 * 
	 * 其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 
	 * 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面
	 * 这么分析完之后，大家可以发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
	 * 那么本题就和我们刚刚讲过的这道题目动态规划：1143.最长公共子序列 就是一样一样的了。
	 */
	public static int maxUncrossedLines(int[] nums1, int[] nums2) {

    	//dp[i][j]：表示nums1[0,i]和nums2[0,j]的最长公共子序列
    	//上述表示中，nums1[0,i]表示nums1长度为i的前缀，nums2[0,j]表示nums2长度为j的前缀
    	
    	int m = nums1.length;
    	int n = nums2.length;
    	int[][] dp = new int[m + 1][n + 1];
    	/**
    	 * 递推公示：if(nums1[i - 1] == nums2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1
    	 * 	      else  dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])
    	 * 初始化：i=0或j=0时 dp[i][j]=0
    	 */
    	for(int i = 1;i <= m;i++) {
    		for(int j = 1;j <= n;j++) {
    			dp[i][j] = nums1[i - 1] == nums2[j - 1] ? 
    					dp[i - 1][j - 1] + 1 : 
    						Math.max(dp[i - 1][j],dp[i][j - 1]);
    		}
    	}
  
    	return dp[m][n];
    }
}
